package oj;

import bin_tree.BST;

import java.util.NoSuchElementException;

public class Num450 {
    private int size;
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }else if(key< root.val){
           root.left= deleteNode(root.left,key);
           return root;
        }else if(key>root.val){
            root.right=deleteNode(root.right,key);
            return root;
        }else {
            if(root.left==null){
                TreeNode right=root.right;
                root.right=null;
                size--;
                return right;
            }
            if(root.right==null){
                TreeNode left=root.left;
                root.left=null;
                size--;
                return left;
            }
            TreeNode successor=minimum(root.right);
            successor.right=removeMin(root.right);
            successor.left=root.left;
            root.left=root.right=null;
            return successor;

        }

    }
    private TreeNode minimum(TreeNode root) {
        if(root.left==null){
            return root;
        }
        return minimum(root.left);
    }
    private TreeNode removeMin(TreeNode root) {
        if(root.left==null){
            //此时root为最小值节点
            //将右树返回
           TreeNode right=root.right;
            //断枝
            root.right=null;
            size--;
            return right;
        }
        root.left= removeMin(root.left);
        return root;
    }
}
